1. Field of the Invention
The present invention relates to data encoding and data decoding employed in transmission systems, and, more particularly, to a servo block code for an encoder and a related trellis for a maximum-likelihood detector used in conjunction with a decoder.
2. Description of the Related Art
Many digital transmission systems commonly employ maximum-likelihood sequence detection to enhance detection of digital data represented by a sequence of symbols (each symbol made up of a group of bits). The symbol bits are transferred as a signal through a transmission (communication) channel in which noise is typically added to the transmitted signal. For example, magnetic recording systems first encode data into symbol bits that are recorded on a magnetic medium. Writing data to, storing data in, and reading data from the magnetic medium may be considered a transmission channel that has an associated frequency response. A signal may then be read from the magnetic medium as a sampled signal (i.e., a sequence of output samples) representing the stored data (stored symbol bits). Magnetic recording systems for disk drives read and detect data from tracks on the magnetic medium (disk). Each track comprises user (xe2x80x9creadxe2x80x9d) data sectors as well as system dedicated control (e.g., xe2x80x9cservoxe2x80x9d) data sectors embedded between read sectors. Servo data sectors store servo data that is a form of control data the recording system uses 1) to search for tracks (during seek mode) and 2) to position a read head over the track on the magnetic medium. Some magnetic recording systems of the prior art employ digital signal processing to detect the stored servo data, while others may employ analog techniques.
FIG. 1 shows servo processing of a magnetic recording system 100. A portion of the servo data is received by a servo data encoder 101 (shown as a 1/N encoder) that encodes the portion using a rate 1/N code that is described subsequently. The remaining, non-encoded portion and encoded portion of the servo data are further processed by the magnetic write head 102 and, then recorded on the magnetic is medium 110 A magnetic read head 103 reads the information from the magnetic recording medium 110 as an analog signal.
FIG. 2 shows a format for recording the servo data in the servo data sector of magnetic recording medium 110. Servo data may include a preamble 201 that is a sequence of bits from which timing and gain information is recovered. Timing and gain information allows the magnetic read head 103 to obtain gain and phase lock relative to the incoming analog signal provided from a track of the magnetic medium 110. Also shown in FIG. 2 is a burst demodulation field 204 that contains burst data. Burst data may be used by the magnetic read head 103 to detect whether the magnetic read head 103 is positioned directly over the center of a track.
The preamble 201 may be followed by an encoded servo address mark (SAM) 202, which in turn may be followed by encoded Gray data 203 for the servo sector. The SAM 202 comprises a predetermined bit pattern to identify the sector as containing servo data, and may be employed to reset a framing clock used by the magnetic read head 103 to read tracks/sectors from the magnetic recording medium 110. The Gray data 203 represents the track number and cylinder information of the magnetic recording medium, and may be used by the magnetic read head 103 to avoid errors when reading adjacent tracks during seek mode. The SAM 202 and Gray data 203 are usually the portions of the servo data that are encoded as sequences of symbol bits before being recorded, on the magnetic recording medium 110.
Returning to FIG. 1, magnetic read head 103 may provide a sampled analog signal representing the recorded and encoded servo data as output channel samples. The term xe2x80x9coutput channel samplexe2x80x9d indicates that the data has passed through a transmission channel (e.g., magnetic medium 110) that has a form of frequency response (possibly having memory). This type of transmission channel (possibly including a frequency response of a subsequent equalizer) may be termed a partial response channel. The signal representing the encoded servo data has an added noise component and added signal distortion caused by passing the signal through the channel""s frequency response. To partially correct for variations in the channel""s frequency response or for frequency response characteristics of the circuitry of magnetic read head 103, the output channel samples may be applied to equalizer 104. The equalized output channel samples are then applied to a partial-response, maximum-likelihood (PRML) detector 105.
The PRML detector 105 employs an algorithm, such as the Viterbi algorithm (VA), to detect the sequence of symbol bits representing, for example, the encoded SAM 202 and encoded Gray data 203 from the output channel samples. Servo data decoder 106 (shown as a 1/N decoder) receives the detected symbol sequence from PRML detector 105 and decodes the sequence of symbol bits to reconstruct the servo data. Also shown is the burst demodulator 107, which extracts the burst demodulation data from the equalized output channel samples provided by equalizer 104.
Both the SAM 202 and Gray data 203 are encoded by the servo data encoder 101 by mapping each input bit to N output symbol bits, giving a coding rate of (1/N). For example, the biphase code of the prior art maps a xe2x80x9c1xe2x80x9d to a xe2x80x9c1100xe2x80x9d sequence, and a xe2x80x9c0xe2x80x9d to a xe2x80x9c0011xe2x80x9d sequence. Such biphase code has a rate (1/4), and such biphase code is described in, for example, U.S. Pat. No. 5,661,760. As the coding rate (1/N) approaches unity, less redundancy, and so less format overhead, is introduced by the encoding process when recording the servo data.
The Viterbi algorithm (VA) employed by PRML detector 105 provides a maximum a posteriori estimate of a state sequence of a finite-state, discrete-time Markov process observed in noise. Given a received sequence of channel output samples of a signal corrupted with additive noise, the VA finds a sequence of symbol bits which is xe2x80x9cclosestxe2x80x9d to the received sequence of channel output samples. For the VA, closest is relative to a predefined metric. As is known, in a communication channel with additive white gaussian noise (AWGN), the VA may be the optimal, maximum-likelihood sequence-detection algorithm. The VA forms a trellis corresponding to possible states (portion of received symbol bits in the sequence) for each received output channel symbol per unit increment in time (i.e., clock cycle). Transitions between states in the trellis are usually represented by a trellis diagram in which the number of bits (corresponding to output channel samples and detected symbol bits) for a state is equivalent to the memory of the partial response channel. Transitions are xe2x80x9cweightedxe2x80x9d according to the predefined metric, and Euclidean distance may be used as a metric for the trellis structure.
FIG. 3 shows an 8-state trellis employed for a partial response channel having a memory length of three (e.g., an EPR4 channel with response 1+Dxe2x88x92D2xe2x88x92D3). The left column 301 of 3-bit states d(nxe2x88x923,j), d(nxe2x88x922,j), d(nxe2x88x921,j) represents state symbol bits for the channel samples in the PRML detector 105 during a previous clock cycle, while the right column 302 of 3-bit states d(nxe2x88x922,k), d(nxe2x88x921,k), d(n,k) represents state symbol bits for the channel samples during the current clock cycle. For this notation, in xe2x80x9cd(nxe2x88x921,j)xe2x80x9d, the j is the state in the trellis at time (nxe2x88x921) (i.e., one of the states of the left column 301) and in xe2x80x9cd(n,k)xe2x80x9d, k is the state at time n i.e., (i.e., one of the states of the left column 302). The right column 302 includes the state symbol bit, d(n,k) that corresponds to the currently received output channel sample at time n.
Each line, termed a branch, connecting the states in the left and right columns 301 and 302 represents a transition from a previous state of the trellis (i.e., a state of the previous trellis phase) to a current state the trellis (i.e., a state of a current trellis phase). The branch is a portion of a possible path through the trellis, and may be included in more than one path. For example, a branch connects the state #0 (xe2x80x9c000xe2x80x9d) in the left column 301 (the originating state) to state #0 (xe2x80x9c000xe2x80x9d) in the right column 302. This branch represents a potential decision of the detector that not only identifies the current channel sample d(n,0) as being a xe2x80x9c0xe2x80x9d symbol, but also for the path representing the sequence of symbol bits received by the PRML detector 105 up to time n. A branch also connects the state #4 (xe2x80x9c100xe2x80x9d) to state #0 (xe2x80x9c000xe2x80x9d) and represents a potential decision for channel sample d(n,0) being a xe2x80x9c0xe2x80x9d symbol except that now the originating state is xe2x80x9c100xe2x80x9d. Therefore, two paths branches from the previous state may pass through the present state xe2x80x9c000xe2x80x9d.
Similarly, two branches pass through each of the other states in the current trellis phase. Any destination state k ending in a xe2x80x9c0xe2x80x9d represents d(n,k) being the xe2x80x9c0xe2x80x9d symbol for the path going through state k while any destination state k ending in a xe2x80x9c1xe2x80x9d represents d(n,k) equivalent to the xe2x80x9c1xe2x80x9d symbol for the path going through state k. In general, the different possible paths may be represented by a P-state trellis where P=2Q, Q an integer equivalent to the state length (i.e., memory length of the partial response channel). An EPR4 channel has the response 1+Dxe2x88x92D2xe2x88x92D3 and has 3-bit states, requiring a 23=8-state trellis. The EEPR4 channel has the response 1+2Dxe2x88x922D3xe2x88x92D4 and has 4-bit states, requiring a 24=16-state trellis.
The VA recursively performs three steps to detect a path through a trellis corresponding to the received sequence of symbol bits. First, branch metrics for the trellis are calculated for the current states; second, updates for each state metric (sm, which is defined below) are calculated for all states; and, third, survivor paths are determined. The survivor path represents the sequence of symbol bits entering a given state which is closest, according to the Euclidean distance, to the received sequence of symbol bits in noise. The branch metric for a state transition is defined as the Euclidean distance between the received output channel sample (yr[n]) and the ideal channel output sample (yi[n]) corresponding to the transition. To compute the entire, or global, sequence most likely received, the VA recursively calculates and updates state metrics of all states to provide a minimum path metric over several state transitions.
For the VA described above, the branch metric bm (Euclidean distance) of a given transition is defined as the negative logarithm of the likelihood function with respect to the received noisy output channel sample yr[n] and the ideal output channel sample yi[n]. Therefore, the branch metric bm (j,k,n) for the transition from the jth state at time nxe2x88x921 to the kth state at time n, for the exemplary VA algorithm, is given by equation (1):
bm(j,k,n)=xe2x88x92ln ƒ(yr[n]xe2x88x92yi[n])xe2x80x83xe2x80x83(1)
where yi[*] is the ideal channel output sample corresponding to the transition from the jth state to the kth state, and ƒ(*) is the probability density function of the Gaussian noise sequence.
For each state, an add-compare-select (ACS) operation determines the minimum state metric sm for the state based on the previously calculated state metrics of two originating states j and b as well as the branch metrics of the two branches of these states arriving at the current state k. The ACS operation thus determines the state metric sm of state k at time n and can be described by equation (2)
sm(k,n)=min((sm(j,nxe2x88x921)+bm(j,k,n)), (sm(b,nxe2x88x921)+bm(b,k,n)))xe2x80x83xe2x80x83(2)
where j and b are the two possible originating states, sm(j,nxe2x88x921) and sm(b,nxe2x88x921) are the state metrics of the originating states at the previous time (nxe2x88x921), bm(j,k,n) represents the branch metric of the branch connecting states j and k at time n, and bm(b,k,n) represents the branch metric of the branch connecting states b and k at time n.
The VA finds the maximum likelihood sequence by determining the sequence of symbol bits, or path, through the trellis that provides a minimum path metric. The path metric is simply the accumulated branch metrics of different branches encountered by the path through phases of the trellis as different possible paths are considered. The state metric of a given state is the path metric at some particular time if the path includes the given state at that particular time.
A prior art implementation of the ACS operation for a pair of paths (branches) (termed an ACS unit) is shown in FIG. 4. Adders 404 and 405 each provide the sum of the state metric of time nxe2x88x921 and branch metric of time n for a different path (termed a path sum). The comparator 401 compares the path sums provided by adders 404 and 405 and provides an output signal indicating which path sum has a minimum value. Multiplexer (MUX) 402, based on the output signal of the comparator 401, selects as the state metric sm for the current clock cycle (time n) the path sum having the minimum value.
Each branch corresponds to one decision for a symbol d(n,k), which symbol is either a xe2x80x9c0xe2x80x9d for one branch and a xe2x80x9c1xe2x80x9d for the other branch. The decision for selecting one branch over the other branch also corresponds to the decision for the value of ideal output channel sample yi[n]. At time n, the ideal output channel sample is either yi[j,k,n] or yi[b,k,n], where yi[j,k,n] is the ideal output channel sample yi[n] going from state j to state k. The branch metrics are calculated as in equation (1) (i.e., bm(j,k,n)=(yr[n]xe2x88x92yi[j,k,n])2 and bm(b,k,n)=(yr[n]xe2x88x92yi[b,k,n])2 where yr[n] is the received output channel sample at time n). MUX 403, also based on the output signal of the comparator 401, selects either a xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d (corresponding to the symbol value of a branch) as a tentative decision made for the current symbol d(n,k). Therefore, for each state, the comparator 401 selects the minimum state metric for the current clock cycle and also provides a tentative decision for the current data bit d(n,k) in a path memory for storage and shifting.
The operation of the detector (i.e., the transition between states of the trellis) is described with respect to FIGS. 3 and 4 for a single clock cycle. For several clock cycles, the trellis is extended by repeating the basic trellis shown in FIG. 3. Each state in a trellis phase has a corresponding ACS unit. During each clock cycle, the combined ACS units for the corresponding states in the trellis phase shift P=2Q bits, (i.e., d(n,k), (k=0, . . . , Pxe2x88x921), into the path memory. After some decision delay, the PRML detector 105 forms a final decision as to which one of possible paths through this memory has a minimum path metric, and so corresponds to the most likely sequence of received symbol bits.
The present invention relates to circuits and methods for a system that encodes, records, detects, and decodes control data stored on a medium. The control data is encoded and decoded based on aerate M/N code that maps between a block of M data bits of the control data and a block of N symbol bits. The block of N symbol bits form a symbol representing the block of control data, where M is an integer greater than 1 and N is an integer greater than M. The control data may be used for subsequently reading information from the medium after recording. In accordance with an embodiment of the present invention, encoding comprises mapping a block of M bits of a sequence of control data into a block of N symbol bits and storing the N symbol bits on the medium.
In accordance with an exemplary embodiment, a sequence of blocks of N symbol bits is generated from a sequence of channel samples read from a medium and representing information. For this further embodiment, successive portions of the sequence of channel samples are received as transitions between sequential states of a trellis, wherein the sequence of channel samples corresponds to the sequence of blocks of N symbol bits. A set of trellis phases and a set of forcing phases are synchronized to the sequential states, the set of trellis phases corresponding to a block of N channel samples. A path through states of the set of trellis phases is determined in accordance with a maximum-likelihood detection algorithm. The path of states corresponds to a received block of N symbol bits, and wherein, for each trellis phase, a corresponding forcing phase provides, if necessary, a forced decision to the maximum-likelihood detection algorithm for a transition between states in the trellis, the forced decision based on a constraint of the rate (M/N) code.
In accordance with another exemplary embodiment, a sequence of symbol bits is generated from a sequence of channel samples read from a medium, the symbol bits representing a sequence of control data to be used for subsequently reading information from the medium. Blocks of N symbol bits are received, with each block of N symbol bits formed based on a rate (M/N) code applied to a block of M bits of control data. Each block of N symbol bits is mapped into a block of M bits based on the rate (M/N) code to generate the sequence of control data.